{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Title: #Longest Cycle in a Graph"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Difficulty: #Hard"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Category Title: #Algorithms"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Tag Slug: #depth-first-search #graph #topological-sort"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Name Translated: #深度优先搜索 #图 #拓扑排序"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solution Name: longestCycle"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Title: #图中的最长环"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Content:\n",
    "<p>给你一个 <code>n</code>&nbsp;个节点的 <b>有向图</b>&nbsp;，节点编号为&nbsp;<code>0</code>&nbsp;到&nbsp;<code>n - 1</code>&nbsp;，其中每个节点&nbsp;<strong>至多</strong>&nbsp;有一条出边。</p>\n",
    "\n",
    "<p>图用一个大小为 <code>n</code>&nbsp;下标从<strong>&nbsp;0</strong>&nbsp;开始的数组&nbsp;<code>edges</code>&nbsp;表示，节点 <code>i</code>&nbsp;到节点&nbsp;<code>edges[i]</code>&nbsp;之间有一条有向边。如果节点&nbsp;<code>i</code>&nbsp;没有出边，那么&nbsp;<code>edges[i] == -1</code>&nbsp;。</p>\n",
    "\n",
    "<p>请你返回图中的 <strong>最长</strong>&nbsp;环，如果没有任何环，请返回 <code>-1</code>&nbsp;。</p>\n",
    "\n",
    "<p>一个环指的是起点和终点是 <strong>同一个</strong>&nbsp;节点的路径。</p>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>示例 1：</strong></p>\n",
    "\n",
    "<p><img alt=\"\" src=\"https://assets.leetcode.com/uploads/2022/06/08/graph4drawio-5.png\" style=\"width: 335px; height: 191px;\" /></p>\n",
    "\n",
    "<pre>\n",
    "<b>输入：</b>edges = [3,3,4,2,3]\n",
    "<b>输出去：</b>3\n",
    "<b>解释：</b>图中的最长环是：2 -&gt; 4 -&gt; 3 -&gt; 2 。\n",
    "这个环的长度为 3 ，所以返回 3 。\n",
    "</pre>\n",
    "\n",
    "<p><strong>示例 2：</strong></p>\n",
    "\n",
    "<p><img alt=\"\" src=\"https://assets.leetcode.com/uploads/2022/06/07/graph4drawio-1.png\" style=\"width: 171px; height: 161px;\" /></p>\n",
    "\n",
    "<pre>\n",
    "<b>输入：</b>edges = [2,-1,3,1]\n",
    "<b>输出：</b>-1\n",
    "<b>解释：</b>图中没有任何环。\n",
    "</pre>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>提示：</strong></p>\n",
    "\n",
    "<ul>\n",
    "\t<li><code>n == edges.length</code></li>\n",
    "\t<li><code>2 &lt;= n &lt;= 10<sup>5</sup></code></li>\n",
    "\t<li><code>-1 &lt;= edges[i] &lt; n</code></li>\n",
    "\t<li><code>edges[i] != i</code></li>\n",
    "</ul>\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Description: [longest-cycle-in-a-graph](https://leetcode.cn/problems/longest-cycle-in-a-graph/description/)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solutions: [longest-cycle-in-a-graph](https://leetcode.cn/problems/longest-cycle-in-a-graph/solutions/)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "test_cases = ['[3,3,4,2,3]', '[2,-1,3,1]']"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def longestCycle(self, edges: List[int]) -> int:\n",
    "        time = [0] * len(edges)\n",
    "        clock, ans = 1, -1\n",
    "        for x, t in enumerate(time):\n",
    "            if t: continue\n",
    "            start_time = clock\n",
    "            while x >= 0:\n",
    "                if time[x]:  # 重复访问\n",
    "                    if time[x] >= start_time:  # 找到了一个新的环\n",
    "                        ans = max(ans, clock - time[x])\n",
    "                    break\n",
    "                time[x] = clock\n",
    "                clock += 1\n",
    "                x = edges[x]\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class DSU:\n",
    "    def __init__(self,N):\n",
    "        self.parents = [i for i in range(N)]\n",
    "    def find(self,x):\n",
    "        st = x \n",
    "        while x != self.parents[x]:\n",
    "            x = self.parents[x]\n",
    "        self.parents[st] = x\n",
    "        return x \n",
    "    def find_union(self,x,y):\n",
    "        self.parents[self.find(x)] = self.find(y)\n",
    "\n",
    "class Solution:\n",
    "    def longestCycle(self, edges: List[int]) -> int:\n",
    "        # 有向图判定环,使用的是拓扑排序的算法\n",
    "        # 就拓扑排序,排序完成后可以发现那些节点是成环的\n",
    "        innode = [0]*len(edges)\n",
    "        dsu = DSU(len(edges))\n",
    "\n",
    "        for i in range(len(edges)):\n",
    "            if edges[i] != -1:\n",
    "                innode[edges[i]] += 1\n",
    "            # 合并i和edges[i]这两个点\n",
    "            if dsu.find(i) != dsu.find(edges[i]):\n",
    "                dsu.find_union(i,edges[i])\n",
    "        \n",
    "        # 拓扑排序\n",
    "        q = deque()\n",
    "        for i in range(len(innode)):\n",
    "            if innode[i] == 0:\n",
    "                q.append(i)\n",
    "        \n",
    "        while q:\n",
    "            node = q.popleft()\n",
    "            nxt = edges[node]\n",
    "            if nxt != -1:\n",
    "                innode[nxt] -= 1\n",
    "                if innode[nxt] == 0:\n",
    "                    q.append(nxt)\n",
    "        \n",
    "        # 统计最大环\n",
    "        hashmap = {}\n",
    "        res = -inf \n",
    "        for i in range(len(innode)):\n",
    "            if innode[i] != 0:\n",
    "                p = dsu.find(i)\n",
    "                if p in hashmap:\n",
    "                    hashmap[p] += 1\n",
    "                else:\n",
    "                    hashmap[p] = 1\n",
    "                res = max(hashmap[p],res)\n",
    "        if res < 0:\n",
    "            return -1\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def longestCycle(self, edges: List[int]) -> int:\n",
    "        n = len(edges)\n",
    "        # 记录节点入度\n",
    "        indeg = [0] * n\n",
    "        for u in edges:\n",
    "            if u == -1:\n",
    "                continue\n",
    "            indeg[u] += 1\n",
    "\n",
    "        q=[i for i in range(n) if indeg[i]==0]\n",
    "\n",
    "        while q:\n",
    "            x=q.pop()\n",
    "            v=edges[x]\n",
    "            if v==-1:\n",
    "                continue\n",
    "            indeg[v]-=1\n",
    "            if indeg[v]==0:\n",
    "                q.append(v)\n",
    "        if max(indeg)==0:\n",
    "            return -1\n",
    "        def BFS(root):\n",
    "            step=0\n",
    "            while True:\n",
    "                if root in visited:\n",
    "                    return step\n",
    "                visited.add(root)\n",
    "                root=edges[root]\n",
    "                step+=1\n",
    "        ans=0\n",
    "        visited=set()\n",
    "        for i in range(n):\n",
    "            if i not in visited and indeg[i]!=0:\n",
    "                ans=max(ans,BFS(i))\n",
    "            \n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def longestCycle(self, edges: List[int]) -> int:\n",
    "        n = len(edges)\n",
    "        inDeg = [0] * n\n",
    "        for u, v in enumerate(edges):\n",
    "            if v != -1:\n",
    "                inDeg[v] += 1\n",
    "\n",
    "        q = [i for i in range(n) if not inDeg[i]]\n",
    "        while q:\n",
    "            u = q.pop()\n",
    "            v = edges[u]\n",
    "            if v == -1:\n",
    "                continue\n",
    "            inDeg[v] -= 1\n",
    "            if not inDeg[v]:\n",
    "                q.append(v)\n",
    "        \n",
    "        if not max(inDeg): return -1\n",
    "\n",
    "        ans = 0\n",
    "        vis = set()\n",
    "        for i in range(n):\n",
    "            if i in vis or not inDeg[i]:\n",
    "                continue\n",
    "            \n",
    "            vis.add(i)\n",
    "            cnt = 1\n",
    "            while 1:\n",
    "                v = edges[i]\n",
    "                if v in vis:\n",
    "                    break\n",
    "                vis.add(v)\n",
    "                cnt += 1\n",
    "                i = v\n",
    "            if cnt > ans:\n",
    "                ans = cnt\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def longestCycle(self, edges: List[int]) -> int:\n",
    "        n = len(edges)\n",
    "        g =[[] for _ in range(n)]\n",
    "        deg =[0]*n\n",
    "        for i,x in enumerate(edges):\n",
    "            if x!=-1:\n",
    "                g[i].append(x)\n",
    "                deg[x]+=1\n",
    "\n",
    "        q =deque()\n",
    "        for i,x in enumerate(deg):\n",
    "            if x == 0:\n",
    "                q.append(i)\n",
    "\n",
    "        while q:\n",
    "            node =q.popleft()\n",
    "            for x in g[node]:\n",
    "                deg[x]-=1\n",
    "                if deg[x]==0:\n",
    "                    q.append(x)\n",
    "\n",
    "        ans = -1 \n",
    "\n",
    "        for i,x in enumerate(deg):\n",
    "            if x:\n",
    "                t = i\n",
    "                cnt =1\n",
    "                deg[i]=0\n",
    "                while True:\n",
    "                    t = edges[t]\n",
    "                    deg[t]=0\n",
    "                    if t ==i:\n",
    "                        break\n",
    "                    cnt+=1\n",
    "                ans = max(cnt,ans)\n",
    "        return ans\n",
    "                \n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def longestCycle(self, edges: List[int]) -> int:\n",
    "        ans = -1\n",
    "\n",
    "        for u in range(len(edges)):\n",
    "            if edges[u] == -1:\n",
    "                continue\n",
    "            timestamps = defaultdict(int)\n",
    "            timestamps[u] = cnt = 0\n",
    "            while edges[u] != -1:\n",
    "                cnt += 1\n",
    "                edges[u], u = -1, edges[u]\n",
    "                if u in timestamps:\n",
    "                    if (v := cnt - timestamps[u]) > ans:\n",
    "                        ans = v\n",
    "                    break\n",
    "                timestamps[u] = cnt\n",
    "        \n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from collections import deque\n",
    "from typing import List\n",
    "\n",
    "# template\n",
    "\"\"\"\n",
    "graph - graph[i] means there is a directed edge from i -> graph[i] if graph[i] != -1\n",
    "\"\"\"\n",
    "\n",
    "def build_reverse_graph(graph, n):\n",
    "    reverse_graph = [[] for _ in range(n)]\n",
    "    for u, v in enumerate(graph):\n",
    "        if v != -1:\n",
    "            reverse_graph[v].append(u)\n",
    "    return reverse_graph\n",
    "\n",
    "def count_in_degs(reverse_graph):\n",
    "    return [len(parents) for parents in reverse_graph]\n",
    "\n",
    "def toposort(graph, indegs):\n",
    "    queue = deque([u for u, deg in enumerate(indegs) if not deg])\n",
    "\n",
    "    while queue:\n",
    "        u = queue.popleft()\n",
    "        v = graph[u]\n",
    "        if v != -1:\n",
    "            indegs[v] -= 1\n",
    "            if not indegs[v]:\n",
    "                queue.append(v)\n",
    "    \n",
    "def find(graph):\n",
    "    n = len(graph)\n",
    "    reverse_graph = build_reverse_graph(graph, n)\n",
    "    in_degs = count_in_degs(reverse_graph)\n",
    "\n",
    "    # toposort to remove nodes that're not on cycles\n",
    "    toposort(graph, in_degs)\n",
    "\n",
    "    # visit the nodes and count cycle sizes\n",
    "    global_max = -1\n",
    "    for u, deg in enumerate(in_degs):\n",
    "        if not deg: continue\n",
    "        cycle_size = 1\n",
    "        in_degs[u] = 0\n",
    "        v = graph[u]\n",
    "        while v != u:\n",
    "            cycle_size += 1\n",
    "            in_degs[v] = 0\n",
    "            v = graph[v]\n",
    "        global_max = max(global_max, cycle_size)\n",
    "    return global_max\n",
    "\n",
    "def get_depth(reverse_graph, node, in_degs):\n",
    "    prev = [node]\n",
    "    depth = -1\n",
    "    while prev:\n",
    "        curr = []\n",
    "        depth += 1\n",
    "        for u in prev:\n",
    "            for v in reverse_graph[u]:\n",
    "                if not in_degs[v]:\n",
    "                    curr.append(v)\n",
    "        prev = curr\n",
    "    return depth\n",
    "\n",
    "class Solution:\n",
    "    def longestCycle(self, edges: List[int]) -> int:\n",
    "        return find(edges)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from collections import deque\n",
    "from typing import Iterable, List, Mapping, Sequence, Tuple, Union\n",
    "\n",
    "\n",
    "SequenceGraph = Sequence[Iterable[int]]\n",
    "MappingGraph = Mapping[int, Iterable[int]]\n",
    "Graph = Union[SequenceGraph, MappingGraph]\n",
    "\n",
    "\n",
    "def cyclePartition(\n",
    "    n: int, graph: Graph, directed: bool\n",
    ") -> Tuple[List[List[int]], List[bool], List[int], List[int]]:\n",
    "    \"\"\"返回基环树森林的环分组信息(环的大小>=2)以及每个点在拓扑排序中的最大深度.\n",
    "\n",
    "    Args:\n",
    "        - n: 图的节点数.\n",
    "        - graph: 图的邻接表表示.\n",
    "        - directed: 图是否有向.\n",
    "\n",
    "    Returns:\n",
    "        - groups: 环分组,每个环的大小>=2.\n",
    "        - inCycle: 每个点是否在环中.\n",
    "        - belong: 每个点所在的环的编号.如果不在环中,则为-1.\n",
    "        - depth: 每个点在拓扑排序中的最大深度,最外层的点深度为0.\n",
    "    \"\"\"\n",
    "\n",
    "    def max(a: int, b: int) -> int:\n",
    "        return a if a > b else b\n",
    "\n",
    "    deg = [0] * n\n",
    "    if directed:\n",
    "        for u in range(n):\n",
    "            for v in graph[u]:\n",
    "                deg[v] += 1\n",
    "    else:\n",
    "        for u in range(n):\n",
    "            for v in graph[u]:\n",
    "                if u < v:\n",
    "                    deg[u] += 1\n",
    "                    deg[v] += 1\n",
    "\n",
    "    startDeg = 0 if directed else 1\n",
    "    queue = deque([i for i in range(n) if deg[i] == startDeg])\n",
    "    visited = [False] * n\n",
    "    depth = [0] * n\n",
    "    while queue:\n",
    "        cur = queue.popleft()\n",
    "        visited[cur] = True\n",
    "        for next_ in graph[cur]:\n",
    "            depth[next_] = max(depth[next_], depth[cur] + 1)\n",
    "            deg[next_] -= 1\n",
    "            if deg[next_] == startDeg:\n",
    "                queue.append(next_)\n",
    "\n",
    "    def dfs(cur: int, path: List[int]) -> None:\n",
    "        stack = [cur]\n",
    "        while stack:\n",
    "            cur = stack.pop()\n",
    "            if visited[cur]:\n",
    "                return\n",
    "            visited[cur] = True\n",
    "            path.append(cur)\n",
    "            for next in graph[cur]:\n",
    "                stack.append(next)\n",
    "\n",
    "    groups = []\n",
    "    for i in range(n):\n",
    "        if visited[i]:\n",
    "            continue\n",
    "        path = []\n",
    "        dfs(i, path)\n",
    "        groups.append(path)\n",
    "\n",
    "    inCycle, belong = [False] * n, [-1] * n\n",
    "    for gid, group in enumerate(groups):\n",
    "        for node in group:\n",
    "            inCycle[node] = True\n",
    "            belong[node] = gid\n",
    "\n",
    "    return groups, inCycle, belong, depth\n",
    "\n",
    "\n",
    "if __name__ == \"__main__\":\n",
    "    # 2360. 图中的最长环\n",
    "    # https://leetcode.cn/problems/longest-cycle-in-a-graph/description/\n",
    "    # !求内向基环树(每个点出度最多为1)的最大环\n",
    "    class Solution:\n",
    "        def longestCycle(self, edges: List[int]) -> int:\n",
    "            \"\"\"\n",
    "            每个节点至多有一条出边\n",
    "            外向基环树最大环\n",
    "            \"\"\"\n",
    "            n = len(edges)\n",
    "            adjList = [[] for _ in range(n)]\n",
    "            for u, v in enumerate(edges):\n",
    "                if v == -1:\n",
    "                    continue\n",
    "                adjList[u].append(v)\n",
    "\n",
    "            cycle, *_ = cyclePartition(n, adjList, directed=True)\n",
    "            return max((len(g) for g in cycle), default=-1)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def longestCycle(self, edges: list[int]) -> int:\n",
    "        from collections import defaultdict\n",
    "        \n",
    "        indegree = defaultdict(int)\n",
    "        for i, n in enumerate(edges):\n",
    "            if n != -1:\n",
    "                indegree[n] += 1\n",
    "        queue = []\n",
    "        for i in range(len(edges)):\n",
    "            if indegree[i] == 0:\n",
    "                queue.append(i)\n",
    "        \n",
    "        # 拓扑排序去掉入度为0的点\n",
    "        while queue:\n",
    "            top = queue.pop()\n",
    "            nxt = edges[top]\n",
    "            if nxt != -1:\n",
    "                indegree[nxt] -= 1\n",
    "                if indegree[nxt] == 0:\n",
    "                    queue.append(nxt)\n",
    "\n",
    "        # 剩下的点都是环\n",
    "        if max(indegree.values()) == 0:\n",
    "            return -1\n",
    "        \n",
    "        def bfs(u):\n",
    "            step = 0\n",
    "            while True:\n",
    "                if u in visited:\n",
    "                    return step\n",
    "                visited.add(u)\n",
    "                u = edges[u]\n",
    "                step += 1\n",
    "        \n",
    "        # 遍历有向环中的所有节点\n",
    "        res = 0 \n",
    "        visited = set()             \n",
    "        for u in range(len(edges)):\n",
    "            if indegree[u] == 0 or u in visited:\n",
    "                continue\n",
    "            circle_len = bfs(u)\n",
    "            res = max(res, circle_len)\n",
    "        \n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def longestCycle(self, edges: List[int]) -> int:\n",
    "        d = {}\n",
    "        for i in range(len(edges)):\n",
    "            l, x = [], i\n",
    "            while x!=-1 and x not in d:\n",
    "                d[x] = None\n",
    "                l.append(x)\n",
    "                if x!=-1: x = edges[x]\n",
    "            p = len(l) if x not in l else l.index(x)\n",
    "            for x in l[:p]: d[x] = (0, -1)\n",
    "            for x in l[p:]: d[x] = (1, len(l)-p)\n",
    "        return max(i[1] for i in d.values())"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def longestCycle(self, edges: List[int]) -> int:\n",
    "        unused_point = {i for i in range(len(edges))}\n",
    "        direction = {i: edges[i] for i in range(len(edges))}\n",
    "        circle_start = set()\n",
    "        color = [0] * len(edges)\n",
    "        c = 0\n",
    "        while unused_point:\n",
    "            c += 1\n",
    "            val = unused_point.pop()\n",
    "            color[val] = c\n",
    "            while True:\n",
    "                val = direction.get(val, None)\n",
    "                if val == -1 or val is None or (color[val] != 0 and color[val] != c):\n",
    "                    break\n",
    "                if color[val] == c:\n",
    "                    circle_start.add(val)\n",
    "                    break\n",
    "                unused_point.discard(val)\n",
    "                color[val] = c\n",
    "        ans = -1\n",
    "        for enter in circle_start:\n",
    "            cnt = 0\n",
    "            val = enter\n",
    "            while True:\n",
    "                val = direction[val]\n",
    "                cnt += 1\n",
    "                if val == enter:\n",
    "                    break\n",
    "            if ans < cnt:\n",
    "                ans = cnt\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def longestCycle(self, edges: List[int]) -> int:\n",
    "        from collections import defaultdict, deque\n",
    "        n = len(edges)\n",
    "        indegree = [0 for _ in range(n)]\n",
    "        graph = defaultdict(list)\n",
    "        for fm, to in enumerate(edges):\n",
    "            if to == -1:\n",
    "                continue\n",
    "            indegree[to] += 1\n",
    "            graph[fm].append(to)\n",
    "        # 拓扑排序 寻找环\n",
    "        root = []\n",
    "        for i in range(n):\n",
    "            if indegree[i] == 0:\n",
    "                root.append(i)\n",
    "        queue = deque(root)\n",
    "        count = 0\n",
    "        while queue:\n",
    "            cur_node = queue.popleft()\n",
    "            count += 1\n",
    "            for next_node in graph[cur_node]:\n",
    "                indegree[next_node] -= 1\n",
    "                if indegree[next_node] == 0:\n",
    "                    queue.append(next_node)\n",
    "        if count == n:\n",
    "            return -1\n",
    "        \n",
    "        node_in_circle = []\n",
    "        for i in range(n):\n",
    "            if indegree[i] != 0:\n",
    "                node_in_circle.append(i)\n",
    "        vis = [False for _ in range(n)]        \n",
    "        def bfs(node):\n",
    "            queue = deque([node])\n",
    "            node_num = 0\n",
    "            while queue:\n",
    "                node = queue.popleft()\n",
    "                vis[node] = True\n",
    "                node_num += 1\n",
    "                for next_node in graph[node]:\n",
    "                    if vis[next_node]:\n",
    "                        return node_num\n",
    "                    queue.append(next_node)\n",
    "        res = 0\n",
    "        for node in node_in_circle:\n",
    "            res = max(res, bfs(node))\n",
    "        return res\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def longestCycle(self, edges: List[int]) -> int:\n",
    "        n = len(edges)\n",
    "        inDeg = [0] * n\n",
    "        adjList = [[] for _ in range(n)]\n",
    "        for u, v in enumerate(edges):\n",
    "            if v != -1:\n",
    "                inDeg[v] += 1\n",
    "                adjList[u].append(v)\n",
    "\n",
    "        q = [i for i, d in enumerate(inDeg) if not d]\n",
    "        unvisited = set(range(n)) - set(q)\n",
    "        while q:\n",
    "            tmp, q = q, []\n",
    "            for u in tmp:\n",
    "                for v in adjList[u]:\n",
    "                    inDeg[v] -= 1\n",
    "                    if not inDeg[v]:\n",
    "                        q.append(v)\n",
    "                        unvisited.discard(v)\n",
    "        \n",
    "        if not unvisited: return -1\n",
    "\n",
    "        ans = 0\n",
    "        for i in range(n):\n",
    "            if i not in unvisited:\n",
    "                continue\n",
    "            \n",
    "            q = [i]\n",
    "            unvisited.discard(i)\n",
    "            cnt = 1\n",
    "            while q:\n",
    "                tmp, q = q, []\n",
    "                for u in tmp:\n",
    "                    for v in adjList[u]:\n",
    "                        if v in unvisited:\n",
    "                            unvisited.discard(v)\n",
    "                            q.append(v)\n",
    "                            cnt += 1\n",
    "            ans = max(ans, cnt)\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def longestCycle(self, edges: List[int]) -> int:\n",
    "        #n_ring = len(edges)\n",
    "        indo = [0 for _ in range(len(edges))]\n",
    "        for e in edges:\n",
    "            if e != -1:\n",
    "                indo[e] += 1\n",
    "        \n",
    "        def dfs(n):\n",
    "            if edges[n] != -1:\n",
    "                indo[edges[n]] -= 1\n",
    "                if indo[edges[n]] == 0:\n",
    "                    dfs(edges[n])\n",
    "            indo[n] -= 1\n",
    "\n",
    "        for i in range(len(edges)):\n",
    "            if indo[i] == 0:\n",
    "                dfs(i)\n",
    "        \n",
    "        max_l = -1\n",
    "        for i in range(len(edges)):\n",
    "            if indo[i] == 1:\n",
    "                n_node = 1\n",
    "                temp = edges[i]\n",
    "                while temp != i:\n",
    "                    n_node += 1\n",
    "                    indo[temp] -= 1\n",
    "                    temp = edges[temp]\n",
    "                indo[i] -= 1\n",
    "                max_l = n_node if n_node > max_l else max_l\n",
    "\n",
    "        return max_l"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "def Tarjan_SCC(n, G):\n",
    "    SCC, S, P = [], [], []\n",
    "    Q, state = list(range(n)), [0] * n\n",
    "    tag = [0] * n\n",
    "    while Q:\n",
    "        node = Q.pop()\n",
    "        if node < 0:\n",
    "            d = state[~node] - 1\n",
    "            if P[-1] > d:\n",
    "                SCC.append(S[d:])\n",
    "                del S[d:]; P.pop()\n",
    "                for v in SCC[-1]:\n",
    "                    state[v] = -1\n",
    "                    tag[v] = len(SCC) - 1\n",
    "        elif state[node] > 0:\n",
    "            while P[-1] > state[node]:\n",
    "                P.pop()\n",
    "        elif state[node] == 0:\n",
    "            S.append(node)\n",
    "            P.append(len(S))\n",
    "            state[node] = len(S)\n",
    "            Q.append(~node)\n",
    "            Q.extend(G[node])\n",
    "    return SCC[::-1], tag\n",
    "\n",
    "class Solution:\n",
    "    def longestCycle(self, edges: List[int]) -> int:\n",
    "        n = len(edges)\n",
    "        g = [[] for _ in range(n)]\n",
    "        for u, v in enumerate(edges):\n",
    "            if v != -1:\n",
    "                g[u].append(v)\n",
    "        group, tag = Tarjan_SCC(n, g)\n",
    "        res = max(map(len, group))\n",
    "        return res if res > 1 else -1\n",
    "        print(group)\n",
    "        print(tag)\n",
    "        # res = max(map(len, sg.scc()))\n",
    "        # return res if res > 1 else -1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class scc_graph:\n",
    "\n",
    "    def __init__(self, N):\n",
    "        self.N = N\n",
    "        self.edges = []\n",
    "\n",
    "    def csr(self):\n",
    "        self.start = [0] * (self.N + 1)\n",
    "        self.elist = [0] * len(self.edges)\n",
    "        for e in self.edges:\n",
    "            self.start[e[0] + 1] += 1\n",
    "        for i in range(1, self.N + 1):\n",
    "            self.start[i] += self.start[i - 1]\n",
    "        counter = self.start[:]\n",
    "        for e in self.edges:\n",
    "            self.elist[counter[e[0]]] = e[1]\n",
    "            counter[e[0]] += 1\n",
    "\n",
    "    def add_edge(self, v, w):\n",
    "        self.edges.append((v, w))\n",
    "\n",
    "    def scc_ids(self):\n",
    "        self.csr()\n",
    "        N = self.N\n",
    "        now_ord = group_num = 0\n",
    "        visited = []\n",
    "        low = [0] * N\n",
    "        order = [-1] * N\n",
    "        ids = [0] * N\n",
    "        parent = [-1] * N\n",
    "        stack = []\n",
    "        for i in range(N):\n",
    "            if order[i] == -1:\n",
    "                stack.append(i)\n",
    "                stack.append(i)\n",
    "                while stack:\n",
    "                    v = stack.pop()\n",
    "                    if order[v] == -1:\n",
    "                        low[v] = order[v] = now_ord\n",
    "                        now_ord += 1\n",
    "                        visited.append(v)\n",
    "                        for i in range(self.start[v], self.start[v + 1]):\n",
    "                            to = self.elist[i]\n",
    "                            if order[to] == -1:\n",
    "                                stack.append(to)\n",
    "                                stack.append(to)\n",
    "                                parent[to] = v\n",
    "                            else:\n",
    "                                low[v] = min(low[v], order[to])\n",
    "                    else:\n",
    "                        if low[v] == order[v]:\n",
    "                            while True:\n",
    "                                u = visited.pop()\n",
    "                                order[u] = N\n",
    "                                ids[u] = group_num\n",
    "                                if u == v:\n",
    "                                    break\n",
    "                            group_num += 1\n",
    "                        if parent[v] != -1:\n",
    "                            low[parent[v]] = min(low[parent[v]], low[v])\n",
    "        for i, x in enumerate(ids):\n",
    "            ids[i] = group_num - 1 - x\n",
    "\n",
    "        return group_num, ids\n",
    "\n",
    "    def scc(self):\n",
    "        group_num, ids = self.scc_ids()\n",
    "        groups = [[] for _ in range(group_num)]\n",
    "        for i, x in enumerate(ids):\n",
    "            groups[x].append(i)\n",
    "        return groups\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def longestCycle(self, edges: List[int]) -> int:\n",
    "        n = len(edges)\n",
    "        sg = scc_graph(n)\n",
    "        for u, v in enumerate(edges):\n",
    "            if v != -1:\n",
    "                sg.add_edge(u, v)\n",
    "        res = max(map(len, sg.scc()))\n",
    "        return res if res > 1 else -1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def longestCycle(self, edges: List[int]) -> int:\n",
    "        indegree = defaultdict(int)\n",
    "        relation = defaultdict(list)\n",
    "        node_num = len(edges)\n",
    "        for num,val in enumerate(edges):\n",
    "            if val == -1:\n",
    "                continue\n",
    "            indegree[val] += 1\n",
    "            relation[num].append(val)\n",
    "        q = [x for x in range(node_num) if x not in indegree]\n",
    "        while q:\n",
    "            v = q.pop()\n",
    "            node_num -= 1\n",
    "            for i in relation.get(v, []):\n",
    "                indegree[i] -= 1\n",
    "                if indegree[i] == 0:\n",
    "                    q.append(i)\n",
    "        if node_num == 0:\n",
    "            return -1\n",
    "        not_q = [x for x in indegree if indegree[x] != 0]\n",
    "        visit = set()\n",
    "        ans = 0\n",
    "        \n",
    "        for i in not_q:\n",
    "            if i in visit:\n",
    "                continue\n",
    "            def bfs(node):\n",
    "                step = 0\n",
    "                while True:\n",
    "                    if node in visit:\n",
    "                        return step\n",
    "                    visit.add(node)\n",
    "                    node = relation[node][0]\n",
    "                    step += 1\n",
    "            ans = max(ans, bfs(i))\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Path:\n",
    "\n",
    "    def __init__(self, start, end):\n",
    "        self.start = start\n",
    "        self.end = end\n",
    "        self.length = 1\n",
    "\n",
    "\n",
    "def merge_path(paths: dict[int, Path],  edges: list[int]):\n",
    "    size = len(paths)\n",
    "    action = False\n",
    "    for index in range(size):\n",
    "        p = paths[index]\n",
    "        if p.end == -1 or p.start == p.end:\n",
    "            continue\n",
    "\n",
    "        # next_value = edges[p.end]\n",
    "        next_path = paths[p.end]\n",
    "        if next_path:\n",
    "            action = True\n",
    "            if next_path.start == next_path.end:\n",
    "                #已经成环\n",
    "                p.end = -1\n",
    "            else:\n",
    "                p.length = p.length + next_path.length\n",
    "                p.end = next_path.end\n",
    "    return action\n",
    "\n",
    "\n",
    "class Solution:\n",
    "\n",
    "    def longestCycle(self, edges: list[int]) -> int:\n",
    "        size = len(edges)\n",
    "        paths = [Path(i, edges[i]) for i in range(size)]\n",
    "        start_paths = dict(zip(range(size), paths))\n",
    "        longest = -1\n",
    "        for i in range(size):\n",
    "            action = merge_path(start_paths, edges)\n",
    "            if not action:\n",
    "                break\n",
    "\n",
    "        for path in paths:\n",
    "            if path.start == path.end:\n",
    "                longest = max(path.length, longest)\n",
    "        return longest"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def longestCycle(self, edges: List[int]) -> int:\n",
    "        graph = collections.defaultdict(list)\n",
    "        for n1, n2 in enumerate(edges):\n",
    "            graph[n1].append(n2)\n",
    "        \n",
    "        self.res = -1\n",
    "        def bfs(graph, node):\n",
    "            q = deque([node])\n",
    "            # visited = { node }\n",
    "            step = 0\n",
    "            nodeToStep = {}\n",
    "            while q:\n",
    "                for i in range(len(q)):\n",
    "                    node = q.popleft()\n",
    "                    visited.add(node)\n",
    "                    nodeToStep[node] = step\n",
    "                    for neigh in graph[node]:\n",
    "                        if neigh not in visited:\n",
    "                            q.append(neigh)\n",
    "                        else:\n",
    "                            if neigh in nodeToStep:\n",
    "                                self.res = max(self.res, step - nodeToStep[neigh] + 1)\n",
    "                step += 1\n",
    "        \n",
    "        visited = set()\n",
    "        for node in range(len(edges)):\n",
    "            bfs(graph, node)\n",
    "        \n",
    "        return self.res\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def longestCycle(self, edges: List[int]) -> int:\n",
    "        a = []\n",
    "        d = defaultdict(set)\n",
    "        for i, n in enumerate(edges):\n",
    "            if n == -1:\n",
    "                a.append(i)\n",
    "                continue\n",
    "            d[n].add(i)\n",
    "        while a:\n",
    "            a = [i for n in a if n in d for i in d.pop(n)]\n",
    "\n",
    "        def f(i):\n",
    "            j = edges[i]\n",
    "            if j not in d:\n",
    "                return\n",
    "            d[j].discard(i)\n",
    "            if not d[j]:\n",
    "                del d[j]\n",
    "                f(j)\n",
    "\n",
    "        for i, n in enumerate(edges):\n",
    "            if i not in d:\n",
    "                f(i)\n",
    "\n",
    "        m = -1\n",
    "        while d:\n",
    "            i = d.popitem()[0]\n",
    "            s = {i}\n",
    "            a = 1\n",
    "            while (i := edges[i]) not in s:\n",
    "                s.add(i)\n",
    "                d.pop(i)\n",
    "                a += 1\n",
    "            m = max(m, a)\n",
    "        return m"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def longestCycle(self, edges: List[int]) -> int:\n",
    "        indegree = defaultdict(int)\n",
    "        father = defaultdict(list)\n",
    "        node_num = len(edges)\n",
    "        for i in range(node_num):\n",
    "            if edges[i] == -1:\n",
    "                continue\n",
    "            indegree[edges[i]] += 1\n",
    "            father[i].append(edges[i])\n",
    "        stack = [x for x in range(node_num) if x not in indegree]\n",
    "        while stack:\n",
    "            vertex = stack.pop()\n",
    "            node_num -= 1\n",
    "            for i in father.get(vertex, []):\n",
    "                indegree[i] -= 1\n",
    "                if indegree[i] == 0:\n",
    "                    stack.append(i)\n",
    "        if node_num == 0:\n",
    "            return -1\n",
    "        indegree_remove_zero = {x:indegree[x] for x in indegree if indegree[x] != 0}\n",
    "        # print(\"in_zero:\", indegree_remove_zero)\n",
    "        visit = set()\n",
    "        ans = 0\n",
    "        for i in indegree_remove_zero:\n",
    "            def bfs(node):\n",
    "                step = 0\n",
    "                while True:\n",
    "                    if node in visit:\n",
    "                        return step\n",
    "                    visit.add(node)\n",
    "                    node = father[node][0]\n",
    "                    step += 1\n",
    "            if i in visit:\n",
    "                continue\n",
    "            ans = max(ans, bfs(i))\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def longestCycle(self, edges: List[int]) -> int:\n",
    "        n=len(edges)\n",
    "        g=defaultdict(list)\n",
    "        ind=[0]*n\n",
    "        out=[0]*n\n",
    "        for i,v in enumerate(edges):\n",
    "            if v!=-1:\n",
    "                g[i].append(v)\n",
    "                ind[v]+=1\n",
    "                out[i]+=1                \n",
    "        \n",
    "        used=set()        \n",
    "        def tuopu():\n",
    "            queue = deque([i for i in range(n) if ind[i] == 0])\n",
    "            while queue:\n",
    "                v = queue.popleft()\n",
    "                used.add(v)\n",
    "                for u in g[v]:\n",
    "                    ind[u] -= 1\n",
    "                    if ind[u] == 0:\n",
    "                        queue.append(u)\n",
    "                    \n",
    "        def bfs(s):\n",
    "            res=-1\n",
    "            time=[0]*n\n",
    "            q=deque([(0,s)])\n",
    "            vis=set([s])\n",
    "            while q:\n",
    "                d,v=q.popleft()\n",
    "                for nex in g[v]:\n",
    "                    if nex not in vis:\n",
    "                        if time[v]==0:\n",
    "                            time[v]=d\n",
    "                        vis.add(v)\n",
    "                        q.append((d+1,nex))\n",
    "                    else:\n",
    "                        res=max(res,d+1-time[nex])\n",
    "            vis1.update(vis)\n",
    "            return res\n",
    "\n",
    "        tuopu()                \n",
    "        vis1=set()        \n",
    "        res=-1\n",
    "        for i in range(n):\n",
    "            if i not in used and i not in vis1:\n",
    "                res=max(res,bfs(i))\n",
    "        return res\n",
    "        \n",
    "        \n",
    "            \n",
    "        \n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "\n",
    "# import time\n",
    "class Solution:\n",
    "    def longestCycle(self, edges: List[int]) -> int:\n",
    "        def buildTopo(conditions, n):\n",
    "            tree = defaultdict(set)\n",
    "            pre_num = [0] * n\n",
    "            for x, y in enumerate(conditions):\n",
    "                if y != -1 and y not in tree[x]:\n",
    "                    tree[x].add(y)\n",
    "                    pre_num[y] += 1\n",
    "            queue = deque([i for i in range(n) if pre_num[i] == 0])\n",
    "            ans = set([i for i in range(n)])\n",
    "            while len(queue):\n",
    "                q = queue.popleft()\n",
    "                ans.remove(q)\n",
    "                for x in tree[q]:\n",
    "                    pre_num[x] -= 1\n",
    "                    if pre_num[x] == 0:\n",
    "                        queue.append(x)\n",
    "            return list(ans)\n",
    "        n = len(edges)\n",
    "        # start = time.time_ns()\n",
    "        remain = buildTopo(edges, n)\n",
    "        # print((time.time_ns() - start) / (1000 * 1000))\n",
    "        # print(left)\n",
    "        flag = {k: 0 for k in remain}\n",
    "        ans = -1\n",
    "        for x in remain:\n",
    "            if flag[x] > 0: continue\n",
    "            length = 0\n",
    "            while flag[x] == 0:\n",
    "                flag[x] = 1\n",
    "                length += 1\n",
    "                x = edges[x]\n",
    "            ans = max(ans, length)\n",
    "        # print((time.time_ns() - start) / (1000 * 1000))\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def longestCycle(self, edges: List[int]) -> int:\n",
    "        #拓扑排序+并查集\n",
    "\n",
    "        # 首先使用拓扑排序找到所有环（可能一个环也可能多个环）\n",
    "        graph = {}\n",
    "        n = len(edges)\n",
    "        inDegree = [0]*n\n",
    "        for i,j in enumerate(edges):\n",
    "            if j < 0:\n",
    "                continue\n",
    "            inDegree[j] += 1\n",
    "            graph[i] = j\n",
    "        queue = deque()\n",
    "        for i,j in enumerate(inDegree):\n",
    "            if j == 0:\n",
    "                queue.append(i)\n",
    "    \n",
    "        # bfs删选在环上的点\n",
    "        while queue:\n",
    "            cur = queue.pop()\n",
    "            if cur not in graph:\n",
    "                continue\n",
    "            new = graph[cur]\n",
    "            del graph[cur]\n",
    "            inDegree[new] -= 1\n",
    "            if inDegree[new] == 0:\n",
    "                queue.appendleft(new)\n",
    "\n",
    "        if not graph:\n",
    "            return -1\n",
    "        # 并查集部分\n",
    "        parent = {k:k for k in graph}\n",
    "        rank = {k:1 for k in graph}\n",
    "        def find(i):\n",
    "            if parent[i]!=i:\n",
    "                parent[i] = find(parent[i])\n",
    "            return parent[i]\n",
    "        def merge(i,j):\n",
    "            ri,rj = find(i),find(j)\n",
    "            if ri != rj:\n",
    "                parent[rj] = ri\n",
    "                rank[ri] += rank[rj]\n",
    "                rank[rj] = 0\n",
    "        for k,v in graph.items():\n",
    "            merge(k,v)\n",
    "        return max(rank.values())\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "        \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class TarjanCC:\n",
    "    def __init__(self):\n",
    "        return\n",
    "\n",
    "    @staticmethod\n",
    "    def get_strongly_connected_component_bfs(n: int, edge: List[List[int]]) -> (int, DefaultDict[int, Set[int]], List[int]):\n",
    "        # 模板：Tarjan求解有向图的强连通分量 edge为有向边要求无自环与重边\n",
    "        dfs_id = 0\n",
    "        order, low = [inf] * n, [inf] * n\n",
    "        visit = [0] * n\n",
    "        out = []\n",
    "        in_stack = [0] * n\n",
    "        scc_id = 0\n",
    "        scc_node_id = defaultdict(set)\n",
    "        node_scc_id = [-1] * n\n",
    "        parent = [-1]*n\n",
    "        for node in range(n):\n",
    "            if not visit[node]:\n",
    "                stack = [[node, 0]]\n",
    "                while stack:\n",
    "                    cur, ind = stack[-1]\n",
    "                    if not visit[cur]:\n",
    "                        visit[cur] = 1\n",
    "                        order[cur] = low[cur] = dfs_id\n",
    "                        dfs_id += 1\n",
    "                        out.append(cur)\n",
    "                        in_stack[cur] = 1\n",
    "                    if ind == len(edge[cur]):\n",
    "                        stack.pop()\n",
    "                        if order[cur] == low[cur]:\n",
    "                            while out:\n",
    "                                top = out.pop()\n",
    "                                in_stack[top] = 0\n",
    "                                scc_node_id[scc_id].add(top)\n",
    "                                node_scc_id[top] = scc_id\n",
    "                                if top == cur:\n",
    "                                    break\n",
    "                            scc_id += 1\n",
    "\n",
    "                        cur, nex = parent[cur], cur\n",
    "                        if cur != -1:\n",
    "                            low[cur] = low[cur] if low[cur] < low[nex] else low[nex]\n",
    "                    else:\n",
    "                        nex = edge[cur][ind]\n",
    "                        stack[-1][-1] += 1\n",
    "                        if not visit[nex]:\n",
    "                            parent[nex] = cur\n",
    "                            stack.append([nex, 0])\n",
    "                        elif in_stack[nex]:\n",
    "                            low[cur] = low[cur] if low[cur] < order[nex] else order[nex]  # 注意这里是order\n",
    "\n",
    "        # 建立新图\n",
    "        new_dct = [set() for _ in range(scc_id)]\n",
    "        for i in range(n):\n",
    "            for j in edge[i]:\n",
    "                a, b = node_scc_id[i], node_scc_id[j]\n",
    "                if a != b:\n",
    "                    new_dct[b].add(a)\n",
    "        new_degree = [0]*scc_id\n",
    "        for i in range(scc_id):\n",
    "            for j in new_dct[i]:\n",
    "                new_degree[j] += 1\n",
    "        # SCC的数量，分组，每个结点对应的SCC编号\n",
    "        return scc_id, scc_node_id, node_scc_id\n",
    "\n",
    "class Solution:\n",
    "    def longestCycle(self, edges: List[int]) -> int:\n",
    "\n",
    "        n = len(edges)\n",
    "        dct = [[] for _ in range(n)]\n",
    "        for i in range(n):\n",
    "            if edges[i] != -1:\n",
    "                dct[i].append(edges[i])\n",
    "\n",
    "        scc_id, scc_node_id, node_scc_id = TarjanCC().get_strongly_connected_component_bfs(n, dct)\n",
    "        cnt= Counter(node_scc_id)\n",
    "        lst = [va for va in cnt.values() if va > 1]\n",
    " \n",
    "        return max(lst) if lst else -1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def longestCycle(self, es: List[int]) -> int:\n",
    "        n=len(es);deg=[0]*(n);g={}\n",
    "        vis=[0]*(n) #for dfs\n",
    "        for u,v in enumerate(es):\n",
    "            if v!=-1:deg[v]+=1;g[u]=v\n",
    "        \n",
    "        # topo sort\n",
    "        q=deque([i for i in range(n) if deg[i]==0])\n",
    "        while q:\n",
    "            u=q.popleft();vis[u]=1\n",
    "            if u not in g:continue\n",
    "            deg[g[u]]-=1\n",
    "            if deg[g[u]]==0:vis[g[u]]=1;q.append(g[u])\n",
    "        \n",
    "        def bfs():\n",
    "            z=0\n",
    "            while q:\n",
    "                u=q.popleft()\n",
    "                if u not in g:continue\n",
    "                if deg[g[u]]:\n",
    "                    z+=1;deg[g[u]]-=1;q.append(g[u])\n",
    "            self.z=max(self.z,z)\n",
    "        def dfs(i,cnt):\n",
    "            if vis[i]:self.z=max(self.z,cnt)\n",
    "            else:\n",
    "                vis[i]=1;dfs(g[i],cnt+1)\n",
    "        self.z=-1\n",
    "        for i in range(n):\n",
    "            if deg[i]:q.append(i);bfs()\n",
    "            # if vis[i]==0:dfs(i,0)\n",
    "        return self.z"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from types import GeneratorType\n",
    "\n",
    "def bootstrap(f, stack=[]):\n",
    "    def wrappedfunc(*args, **kwargs):\n",
    "        if stack:\n",
    "            return f(*args, **kwargs)\n",
    "        else:\n",
    "            to = f(*args, **kwargs)\n",
    "            while True:\n",
    "                if type(to) is GeneratorType:\n",
    "                    stack.append(to)\n",
    "                    to = next(to)\n",
    "                else:\n",
    "                    stack.pop()\n",
    "                    if not stack:\n",
    "                        break\n",
    "                    to = stack[-1].send(to)\n",
    "            return to\n",
    "\n",
    "    return wrappedfunc\n",
    "\n",
    "def tarjan(g):\n",
    "    n = len(g)\n",
    "    stack = list()\n",
    "    on_stack = [False for _ in range(n)]\n",
    "    index_of = [-1 for _ in range(n)]\n",
    "    lowlink_of = index_of[:]\n",
    "    index = 0\n",
    "\n",
    "    @bootstrap\n",
    "    def strong_connect(v, components):\n",
    "        nonlocal index\n",
    "        index_of[v] = index\n",
    "        lowlink_of[v] = index\n",
    "        index += 1\n",
    "        stack.append(v)\n",
    "        on_stack[v] = True\n",
    "\n",
    "        for w in g[v]:\n",
    "            if index_of[w] == -1:\n",
    "                yield strong_connect(w, components)\n",
    "                lowlink_of[v] = min(lowlink_of[w], lowlink_of[v])\n",
    "            elif on_stack[w]:\n",
    "                lowlink_of[v] = min(index_of[w], lowlink_of[v])\n",
    "\n",
    "        if lowlink_of[v] == index_of[v]:\n",
    "            component = []\n",
    "            w = stack.pop()\n",
    "            on_stack[w] = False\n",
    "            component.append(w)\n",
    "            while w != v:\n",
    "                w = stack.pop()\n",
    "                on_stack[w] = False\n",
    "                component.append(w)\n",
    "            components.append(component)\n",
    "        yield\n",
    "\n",
    "    components = []\n",
    "    for v in range(n):\n",
    "        if index_of[v] == -1:\n",
    "            strong_connect(v, components)\n",
    "\n",
    "    return components\n",
    "\n",
    "class Solution:\n",
    "    def longestCycle(self, edges: List[int]) -> int:\n",
    "        n = len(edges)\n",
    "        g = [list() for _ in range(n)]\n",
    "        for i in range(n):\n",
    "            if edges[i] != -1:\n",
    "                g[i].append(edges[i])\n",
    "        components = tarjan(g)\n",
    "        res = max([len(c) for c in components])\n",
    "        if res == 1:\n",
    "            return -1\n",
    "        return res\n",
    "                \n",
    "            \n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    # def longestCycle(self, edges: List[int]) -> int:\n",
    "       \n",
    "    #     path = []\n",
    "    #     visit = [False for _ in range(len(edges))]\n",
    "        \n",
    "    #     self.maxCycle = -1\n",
    "        \n",
    "    #     def traverse(edges,node, path): \n",
    "    #         if edges[node] == -1:\n",
    "    #             visit[node] = True\n",
    "    #             return   \n",
    "    #         if visit[node] and node in path:\n",
    "    #             # self.hasCycle = True\n",
    "    #             self.maxCycle = max(self.maxCycle, len(path) - path.index(node))\n",
    "    #             return\n",
    "    #         elif visit[node]:\n",
    "    #             return \n",
    "            \n",
    "    #         visit[node] = True\n",
    "    #         # path.append(node)\n",
    "            \n",
    "    #         traverse(edges,edges[node],path+[node])\n",
    "    #         # for i in graph[node]:\n",
    "    #         #     traverse(graph,i)\n",
    "    #         # path.pop()  \n",
    "          \n",
    "    #     for i in range(len(edges)):\n",
    "    #         traverse(edges, i, path)\n",
    "        \n",
    "    #     return self.maxCycle\n",
    "\n",
    "    def dfs(self, edges, node, path):\n",
    "        if edges[node] == -1:\n",
    "            self.visit[node] = True\n",
    "            return \n",
    "        if self.visit[node] and node in path:\n",
    "            self.max_cycle = max(self.max_cycle, \n",
    "                                 len(path)  - path.index(node))\n",
    "            return\n",
    "        elif self.visit[node]:\n",
    "            return \n",
    "        \n",
    "        self.visit[node] = True\n",
    "        path.append(node)\n",
    "        self.dfs(edges, edges[node], path)  \n",
    "\n",
    "\n",
    "    def longestCycle(self, edges) -> int:\n",
    "        self.visit = [False for _ in range(len(edges))]\n",
    "        self.max_cycle = -1\n",
    "        for i in range(len(edges)):\n",
    "            self.dfs(edges, i, [])\n",
    "            \n",
    "        \n",
    "        return self.max_cycle\n",
    "\n",
    "        \n",
    "\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "\n",
    "    def init(self, n, edges):\n",
    "        self.vis = [0] * n\n",
    "        self.in_stk = [0] * n\n",
    "        self.edges = edges\n",
    "        self.ans = -1\n",
    "\n",
    "    def dfs(self, u, depth):\n",
    "        self.vis[u] = 1\n",
    "        self.in_stk[u] = depth\n",
    "        j = self.edges[u]\n",
    "        if j != -1:\n",
    "            if not self.vis[j]:\n",
    "                self.dfs(j, depth + 1)\n",
    "            elif self.in_stk[j]:\n",
    "                self.ans = max(self.ans, depth + 1 - self.in_stk[j])\n",
    "        self.in_stk[u] = 0\n",
    "\n",
    "    def longestCycle(self, edges: List[int]) -> int:\n",
    "        n = len(edges)\n",
    "        self.init(n, edges)\n",
    "\n",
    "        for i in range(n):\n",
    "            if not self.vis[i]:\n",
    "                self.dfs(i, 1)\n",
    "        \n",
    "        return self.ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def huan(self, edges, node, ans):\n",
    "        #print(node, ans)\n",
    "        n = edges[node]\n",
    "        if n == -1:\n",
    "            return -1\n",
    "        if ans[n] == -1:\n",
    "            ans[n] = ans[node] + 1\n",
    "            k = self.huan(edges, n, ans)\n",
    "            if k == -1:\n",
    "                ans[n] = -1\n",
    "            return k\n",
    "        else:\n",
    "            return ans[node] - ans[n] + 1\n",
    "    def longestCycle(self, edges: List[int]) -> int:\n",
    "        ans = []\n",
    "        for i in range(len(edges)):\n",
    "            ans.append(-1)\n",
    "        a = -1\n",
    "        for i in range(len(edges)):\n",
    "            if ans[i] == -1:\n",
    "                ans[i] = 0\n",
    "                k = self.huan(edges, i, ans)\n",
    "                ans[i] = -1\n",
    "                if k > a:\n",
    "                    a = k\n",
    "        return a"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    # def longestCycle(self, edges: List[int]) -> int:\n",
    "       \n",
    "    #     path = []\n",
    "    #     visit = [False for _ in range(len(edges))]\n",
    "        \n",
    "    #     self.maxCycle = -1\n",
    "        \n",
    "    #     def traverse(edges,node, path): \n",
    "    #         if edges[node] == -1:\n",
    "    #             visit[node] = True\n",
    "    #             return   \n",
    "    #         if visit[node] and node in path:\n",
    "    #             # self.hasCycle = True\n",
    "    #             self.maxCycle = max(self.maxCycle, len(path) - path.index(node))\n",
    "    #             return\n",
    "    #         elif visit[node]:\n",
    "    #             return \n",
    "            \n",
    "    #         visit[node] = True\n",
    "    #         # path.append(node)\n",
    "            \n",
    "    #         traverse(edges,edges[node],path+[node])\n",
    "    #         # for i in graph[node]:\n",
    "    #         #     traverse(graph,i)\n",
    "    #         # path.pop()  \n",
    "          \n",
    "    #     for i in range(len(edges)):\n",
    "    #         traverse(edges, i, path)\n",
    "        \n",
    "    #     return self.maxCycle\n",
    "\n",
    "    \n",
    "\n",
    "\n",
    "    def longestCycle(self, edges) -> int:\n",
    "        self.visit = [False for _ in range(len(edges))]\n",
    "        self.max_cycle = -1\n",
    "        def dfs(edges, node, path):\n",
    "            if edges[node] == -1:\n",
    "                self.visit[node] = True\n",
    "                return \n",
    "            if self.visit[node] and node in path:\n",
    "                self.max_cycle = max(self.max_cycle, \n",
    "                                    len(path)  - path.index(node))\n",
    "                return\n",
    "            elif self.visit[node]:\n",
    "                return \n",
    "            \n",
    "            self.visit[node] = True\n",
    "            path.append(node)\n",
    "            dfs(edges, edges[node], path)  \n",
    "        for i in range(len(edges)):\n",
    "            dfs(edges, i, [])\n",
    "\n",
    "            \n",
    "        \n",
    "        return self.max_cycle\n",
    "\n",
    "        \n",
    "\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    # def longestCycle(self, edges: List[int]) -> int:\n",
    "       \n",
    "    #     path = []\n",
    "    #     visit = [False for _ in range(len(edges))]\n",
    "        \n",
    "    #     self.maxCycle = -1\n",
    "        \n",
    "    #     def traverse(edges,node, path): \n",
    "    #         if edges[node] == -1:\n",
    "    #             visit[node] = True\n",
    "    #             return   \n",
    "    #         if visit[node] and node in path:\n",
    "    #             # self.hasCycle = True\n",
    "    #             self.maxCycle = max(self.maxCycle, len(path) - path.index(node))\n",
    "    #             return\n",
    "    #         elif visit[node]:\n",
    "    #             return \n",
    "            \n",
    "    #         visit[node] = True\n",
    "    #         # path.append(node)\n",
    "            \n",
    "    #         traverse(edges,edges[node],path+[node])\n",
    "    #         # for i in graph[node]:\n",
    "    #         #     traverse(graph,i)\n",
    "    #         # path.pop()  \n",
    "          \n",
    "    #     for i in range(len(edges)):\n",
    "    #         traverse(edges, i, path)\n",
    "        \n",
    "    #     return self.maxCycle\n",
    "\n",
    "    \n",
    "\n",
    "\n",
    "    def longestCycle(self, edges) -> int:\n",
    "        visit = [False for _ in range(len(edges))]\n",
    "        onPath = []\n",
    "        self.max_cycle = -1\n",
    "        def dfs(edges, node, path):\n",
    "            if edges[node] == -1:\n",
    "                visit[node] = True\n",
    "                return \n",
    "            if visit[node] and node in path:\n",
    "                self.max_cycle = max(self.max_cycle, \n",
    "                                    len(path)  - path.index(node))\n",
    "                return\n",
    "            elif visit[node]:\n",
    "                return \n",
    "            \n",
    "            visit[node] = True\n",
    "            path.append(node)\n",
    "            dfs(edges, edges[node], path) \n",
    "            path.pop() \n",
    "        for i in range(len(edges)):\n",
    "            dfs(edges, i, onPath)\n",
    "\n",
    "            \n",
    "        \n",
    "        return self.max_cycle\n",
    "\n",
    "        \n",
    "\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def longestCycle(self, edges: List[int]) -> int:\n",
    "        vis = [0 for _ in range(len(edges))]\n",
    "        farst = [-1 for _ in range(len(edges))]\n",
    "        farst_dist = [-1 for _ in range(len(edges))]\n",
    "        res = -1\n",
    "        for i in range(len(edges)):\n",
    "            v, dist = self.dfs(i, edges, vis, farst, farst_dist)\n",
    "            if v == i:\n",
    "                res = max(res, dist)\n",
    "        return res\n",
    "        \n",
    "    \n",
    "    def dfs(self, node, edges, vis, farst, farst_dist):\n",
    "        if farst[node] != -1:\n",
    "            return farst[node], farst_dist[node]\n",
    "        if vis[node] == 2:\n",
    "            farst[node] = node\n",
    "            farst_dist[node] = 0\n",
    "            return node, 0\n",
    "        v = edges[node]\n",
    "        if v == -1:\n",
    "            farst[node] = len(edges)\n",
    "            farst_dist[node] = 0\n",
    "            return farst[node], 0\n",
    "        vis[v] += 1\n",
    "        farst_v, farst_v_dist = self.dfs(v, edges, vis, farst, farst_dist)\n",
    "        farst[node] = farst_v\n",
    "        farst_dist[node] = farst_v_dist + 1\n",
    "        vis[v] -= 1\n",
    "        return farst_v, farst_v_dist + 1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def dfs(self, graph, i, index, edges2index):\n",
    "        if i in edges2index or i in self.visited or graph[i] == -1: \n",
    "            if i in edges2index:\n",
    "                # print(edges2index[i])\n",
    "                self.max_val = max(self.max_val, index - edges2index[i])\n",
    "            return \n",
    "        # print(graph, i)\n",
    "        edges2index[i] = index\n",
    "        self.dfs(graph, graph[i], index + 1, edges2index)\n",
    "        edges2index.pop(i)\n",
    "        self.visited.add(i)\n",
    "\n",
    "    def longestCycle(self, edges: List[int]) -> int:\n",
    "        self.max_val = -1\n",
    "        self.visited = set()\n",
    "        for i in range(len(edges)):\n",
    "            self.dfs(edges, i, 0, {})\n",
    "        return self.max_val"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "'''\n",
    "基环内向树\n",
    "Tarjan算法来求强连通分量 因为一个环就是一个强连通分量\n",
    "'''\n",
    "class Solution:\n",
    "    def longestCycle(self, edges: List[int]) -> int:\n",
    "        n = len(edges)\n",
    "        t = [[0,0] for i in range(n)]\n",
    "        stack = []\n",
    "        clock = 1\n",
    "        ans = -1\n",
    "        def dfs(cur):\n",
    "            nonlocal clock, ans\n",
    "            t[cur] = [clock, clock]\n",
    "            stack.append(cur)\n",
    "            clock += 1\n",
    "            nxt = edges[cur]\n",
    "            if nxt == -1:\n",
    "                stack.pop()\n",
    "                return \n",
    "\n",
    "            if t[nxt][0] == 0:\n",
    "                dfs(nxt)                \n",
    "            t[cur][1] = min(t[cur][1], t[nxt][1])\n",
    "\n",
    "            if t[cur][0] == t[cur][1]:\n",
    "                cnt = 1\n",
    "                while stack[-1] != cur:\n",
    "                    cnt += 1\n",
    "                    stack.pop()\n",
    "\n",
    "                stack.pop()\n",
    "                if cnt > 1:\n",
    "                    ans = max(ans, cnt)\n",
    "\n",
    "        for i in range(n):\n",
    "            if t[i][0] == 0:\n",
    "                dfs(i)\n",
    "        #print(t)\n",
    "        return ans\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def longestCycle(self, edges: List[int]) -> int:\n",
    "\n",
    "        a=[]\n",
    "        b=-1\n",
    "        c = []\n",
    "        def loop(lst,num,a,count):\n",
    "            \n",
    "            if lst[num] == -1:\n",
    "                return -1\n",
    "            elif lst[num] in a:                \n",
    "                return count - a[lst[num]]\n",
    "            else:\n",
    "                a[lst[num]] = count\n",
    "                \n",
    "                return loop(lst,int(lst[num]),a,count+1)\n",
    "        def bird(lst,n):\n",
    "            if lst[n] != -1:\n",
    "                j = lst[n]\n",
    "                lst[n] = -1\n",
    "                return bird(lst,j)\n",
    "            else:\n",
    "                return lst\n",
    "        for i in range(len(edges)):\n",
    "            if edges[i] != -1:\n",
    "\n",
    "                new = loop(edges,i,{},0)\n",
    "                b=max(b,new)\n",
    "                if new != -1:\n",
    "                    edges = bird(edges,i)\n",
    "\n",
    "        return b "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "\n",
    "from collections import defaultdict, deque\n",
    "from typing import DefaultDict, List, Set, Tuple\n",
    "\n",
    "\n",
    "def findCycleAndCalDepth(\n",
    "    n: int, adjList: List[List[int]], deg: List[int], *, isDirected: bool\n",
    ") -> Tuple[List[List[int]], List[int]]:\n",
    "    \"\"\"无/有向基环树森林找环上的点,并记录每个点在拓扑排序中的最大深度,最外层的点深度为0\"\"\"\n",
    "    depth = [0] * n\n",
    "    queue = deque([(i, 0) for i in range(n) if deg[i] == (0 if isDirected else 1)])\n",
    "    visited = [False] * n\n",
    "    while queue:\n",
    "        cur, dist = queue.popleft()\n",
    "        visited[cur] = True\n",
    "        for next in adjList[cur]:\n",
    "            depth[next] = max(depth[next], dist + 1)\n",
    "            deg[next] -= 1\n",
    "            if deg[next] == (0 if isDirected else 1):\n",
    "                queue.append((next, dist + 1))\n",
    "\n",
    "    def dfs(cur: int, path: List[int]) -> None:\n",
    "        if visited[cur]:\n",
    "            return\n",
    "        visited[cur] = True\n",
    "        path.append(cur)\n",
    "        for next in adjList[cur]:\n",
    "            dfs(next, path)\n",
    "\n",
    "    cycleGroup = []\n",
    "    for i in range(n):\n",
    "        if visited[i]:\n",
    "            continue\n",
    "        path = []\n",
    "        dfs(i, path)\n",
    "        cycleGroup.append(path)\n",
    "\n",
    "    return cycleGroup, depth\n",
    "\n",
    "\n",
    "if __name__ == \"__main__\":\n",
    "    # 6135. 图中的最长环\n",
    "    # 求内向基环树(每个点出度最多为1)的最大环\n",
    "    class Solution:\n",
    "        def longestCycle(self, edges: List[int]) -> int:\n",
    "            \"\"\"\n",
    "            每个节点至多有一条出边\n",
    "            外向基环树最大环\n",
    "            \"\"\"\n",
    "            n = len(edges)\n",
    "            adjMap = [[] for _ in range(n)]\n",
    "            deg = [0] * n\n",
    "            for u, v in enumerate(edges):\n",
    "                if v == -1:\n",
    "                    continue\n",
    "                adjMap[u].append(v)\n",
    "                deg[v] += 1\n",
    "            cycle, _ = findCycleAndCalDepth(n, adjMap, deg, isDirected=True)\n",
    "            return max((len(g) for g in cycle), default=-1)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def longestCycle(self, edges: List[int]) -> int:\n",
    "        n = len(edges)\n",
    "        li = [[0,0] for _ in range(n)]\n",
    "        for i,j in enumerate(edges):\n",
    "            if j != -1:\n",
    "                li[i][0]+=1 # 出度\n",
    "                li[j][1]+=1 # 入度\n",
    "        q = deque([i for i, j in enumerate(li) if j[1] ==0])\n",
    "        v = [False]*n\n",
    "        while q:\n",
    "            t = q.popleft()\n",
    "            v[t] = True\n",
    "            if edges[t] == -1:\n",
    "                continue\n",
    "            li[edges[t]][1]-=1\n",
    "            if li[edges[t]][1] == 0:\n",
    "                q.append(edges[t])\n",
    "        vis = [0]*n\n",
    "        def dfs(node,ans):\n",
    "\n",
    "            if vis[node] >0:\n",
    "                return ans -vis[node]\n",
    "            v[node] = True\n",
    "            vis[node] = ans\n",
    "            return dfs(edges[node],ans+1)\n",
    "        ans = -1\n",
    "        for i in range(n):\n",
    "            if v[i]:\n",
    "                continue\n",
    "            ans = max(ans,dfs(i,1))\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "\n",
    "from collections import deque\n",
    "from typing import List, Tuple\n",
    "\n",
    "\n",
    "def findCycleAndCalDepth(\n",
    "    n: int, adjList: List[List[int]], deg: List[int], *, isDirected: bool\n",
    ") -> Tuple[List[List[int]], List[int]]:\n",
    "    \"\"\"无/有向基环树森林找环上的点,并记录每个点在拓扑排序中的最大深度,最外层的点深度为0\"\"\"\n",
    "\n",
    "    def max(a: int, b: int) -> int:\n",
    "        return a if a > b else b\n",
    "\n",
    "    depth = [0] * n\n",
    "    queue = deque([(i, 0) for i in range(n) if deg[i] == (0 if isDirected else 1)])\n",
    "    visited = [False] * n\n",
    "    while queue:\n",
    "        cur, dist = queue.popleft()\n",
    "        visited[cur] = True\n",
    "        for next in adjList[cur]:\n",
    "            depth[next] = max(depth[next], dist + 1)\n",
    "            deg[next] -= 1\n",
    "            if deg[next] == (0 if isDirected else 1):\n",
    "                queue.append((next, dist + 1))\n",
    "\n",
    "    def dfs(cur: int, path: List[int]) -> None:\n",
    "        if visited[cur]:\n",
    "            return\n",
    "        visited[cur] = True\n",
    "        path.append(cur)\n",
    "        for next in adjList[cur]:\n",
    "            dfs(next, path)\n",
    "\n",
    "    cycleGroup = []\n",
    "    for i in range(n):\n",
    "        if visited[i]:\n",
    "            continue\n",
    "        path = []\n",
    "        dfs(i, path)\n",
    "        cycleGroup.append(path)\n",
    "\n",
    "    return cycleGroup, depth\n",
    "\n",
    "\n",
    "if __name__ == \"__main__\":\n",
    "    # 2360. 图中的最长环\n",
    "    # !求内向基环树(每个点出度最多为1)的最大环\n",
    "    class Solution:\n",
    "        def longestCycle(self, edges: List[int]) -> int:\n",
    "            \"\"\"\n",
    "            每个节点至多有一条出边\n",
    "            外向基环树最大环\n",
    "            \"\"\"\n",
    "            n = len(edges)\n",
    "            adjList = [[] for _ in range(n)]\n",
    "            deg = [0] * n\n",
    "            for u, v in enumerate(edges):\n",
    "                if v == -1:\n",
    "                    continue\n",
    "                adjList[u].append(v)\n",
    "                deg[v] += 1\n",
    "\n",
    "            cycle, _ = findCycleAndCalDepth(n, adjList, deg, isDirected=True)\n",
    "            return max((len(g) for g in cycle), default=-1)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "\n",
    "\n",
    "from collections import deque\n",
    "from functools import lru_cache\n",
    "from typing import Iterable, List, Mapping, Sequence, Tuple, Union\n",
    "\n",
    "\n",
    "SequenceGraph = Sequence[Iterable[int]]\n",
    "MappingGraph = Mapping[int, Iterable[int]]\n",
    "Graph = Union[SequenceGraph, MappingGraph]\n",
    "\n",
    "\n",
    "def cyclePartition(\n",
    "    n: int, graph: Graph, directed: bool\n",
    ") -> Tuple[List[List[int]], List[bool], List[int], List[int]]:\n",
    "    \"\"\"返回基环树森林的环分组信息(环的大小>=2)以及每个点在拓扑排序中的最大深度.\n",
    "\n",
    "    Args:\n",
    "        - n: 图的节点数.\n",
    "        - graph: 图的邻接表表示.\n",
    "        - directed: 图是否有向.\n",
    "\n",
    "    Returns:\n",
    "        - groups: 环分组,每个环的大小>=2.\n",
    "        - inCycle: 每个点是否在环中.\n",
    "        - belong: 每个点所在的环的编号.如果不在环中,则为-1.\n",
    "        - depth: 每个点在拓扑排序中的最大深度,最外层的点深度为0.\n",
    "    \"\"\"\n",
    "\n",
    "    def max(a: int, b: int) -> int:\n",
    "        return a if a > b else b\n",
    "\n",
    "    deg = [0] * n\n",
    "    if directed:\n",
    "        for u in range(n):\n",
    "            for v in graph[u]:\n",
    "                deg[v] += 1\n",
    "    else:\n",
    "        for u in range(n):\n",
    "            for v in graph[u]:\n",
    "                if u < v:\n",
    "                    deg[u] += 1\n",
    "                    deg[v] += 1\n",
    "\n",
    "    startDeg = 0 if directed else 1\n",
    "    queue = deque(i for i in range(n) if deg[i] == startDeg)\n",
    "    visited = [False] * n\n",
    "    depth = [0] * n\n",
    "    while queue:\n",
    "        cur = queue.popleft()\n",
    "        visited[cur] = True\n",
    "        for next_ in graph[cur]:\n",
    "            depth[next_] = max(depth[next_], depth[cur] + 1)\n",
    "            deg[next_] -= 1\n",
    "            if deg[next_] == startDeg:\n",
    "                queue.append(next_)\n",
    "\n",
    "    def dfs(cur: int, path: List[int]) -> None:\n",
    "        if visited[cur]:\n",
    "            return\n",
    "        visited[cur] = True\n",
    "        path.append(cur)\n",
    "        for next in graph[cur]:\n",
    "            dfs(next, path)\n",
    "\n",
    "    groups = []\n",
    "    for i in range(n):\n",
    "        if visited[i]:\n",
    "            continue\n",
    "        path = []\n",
    "        dfs(i, path)\n",
    "        groups.append(path)\n",
    "\n",
    "    inCycle, belong = [False] * n, [-1] * n\n",
    "    for gid, group in enumerate(groups):\n",
    "        for node in group:\n",
    "            inCycle[node] = True\n",
    "            belong[node] = gid\n",
    "\n",
    "    return groups, inCycle, belong, depth\n",
    "\n",
    "\n",
    "if __name__ == \"__main__\":\n",
    "    # 2360. 图中的最长环\n",
    "    # https://leetcode.cn/problems/longest-cycle-in-a-graph/description/\n",
    "    # !求内向基环树(每个点出度最多为1)的最大环\n",
    "    class Solution:\n",
    "        def longestCycle(self, edges: List[int]) -> int:\n",
    "            \"\"\"\n",
    "            每个节点至多有一条出边\n",
    "            外向基环树最大环\n",
    "            \"\"\"\n",
    "            n = len(edges)\n",
    "            adjList = [[] for _ in range(n)]\n",
    "            for u, v in enumerate(edges):\n",
    "                if v == -1:\n",
    "                    continue\n",
    "                adjList[u].append(v)\n",
    "\n",
    "            cycle, *_ = cyclePartition(n, adjList, directed=True)\n",
    "            return max((len(g) for g in cycle), default=-1)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "\n",
    "from collections import deque\n",
    "from typing import Iterable, List, Mapping, Sequence, Tuple, Union\n",
    "\n",
    "\n",
    "SequenceGraph = Sequence[Iterable[int]]\n",
    "MappingGraph = Mapping[int, Iterable[int]]\n",
    "Graph = Union[SequenceGraph, MappingGraph]\n",
    "\n",
    "\n",
    "def cyclePartition(\n",
    "    n: int, graph: Graph, isDirected: bool\n",
    ") -> Tuple[List[List[int]], List[bool], List[int], List[int]]:\n",
    "    \"\"\"返回基环树森林的环分组信息(环的大小>=2)以及每个点在拓扑排序中的最大深度.\n",
    "\n",
    "    Args:\n",
    "        - n: 图的节点数.\n",
    "        - graph: 图的邻接表表示.\n",
    "        - isDirected: 图是否有向.\n",
    "\n",
    "    Returns:\n",
    "        - groups: 环分组,每个环的大小>=2.\n",
    "        - inCycle: 每个点是否在环中.\n",
    "        - belong: 每个点所在的环的编号.如果不在环中,则为-1.\n",
    "        - depth: 每个点在拓扑排序中的最大深度,最外层的点深度为0.\n",
    "    \"\"\"\n",
    "\n",
    "    def max(a: int, b: int) -> int:\n",
    "        return a if a > b else b\n",
    "\n",
    "    depth = [0] * n\n",
    "    startDeg = 0 if isDirected else 1\n",
    "    deg = [0] * n\n",
    "    if isDirected:\n",
    "        for u in range(n):\n",
    "            for v in graph[u]:\n",
    "                deg[v] += 1\n",
    "    else:\n",
    "        for u in range(n):\n",
    "            for v in graph[u]:\n",
    "                deg[v] += 1\n",
    "                deg[u] += 1\n",
    "\n",
    "    queue = deque([i for i in range(n) if deg[i] == startDeg])\n",
    "    visited = [False] * n\n",
    "    while queue:\n",
    "        cur = queue.popleft()\n",
    "        visited[cur] = True\n",
    "        for next_ in graph[cur]:\n",
    "            depth[next_] = max(depth[next_], depth[cur] + 1)\n",
    "            deg[next_] -= 1\n",
    "            if deg[next_] == startDeg:\n",
    "                queue.append(next_)\n",
    "\n",
    "    def dfs(cur: int, path: List[int]) -> None:\n",
    "        if visited[cur]:\n",
    "            return\n",
    "        visited[cur] = True\n",
    "        path.append(cur)\n",
    "        for next in graph[cur]:\n",
    "            dfs(next, path)\n",
    "\n",
    "    groups = []\n",
    "    for i in range(n):\n",
    "        if visited[i]:\n",
    "            continue\n",
    "        path = []\n",
    "        dfs(i, path)\n",
    "        groups.append(path)\n",
    "\n",
    "    inCycle, belong = [False] * n, [-1] * n\n",
    "    for gid, group in enumerate(groups):\n",
    "        for node in group:\n",
    "            inCycle[node] = True\n",
    "            belong[node] = gid\n",
    "\n",
    "    return groups, inCycle, belong, depth\n",
    "\n",
    "\n",
    "if __name__ == \"__main__\":\n",
    "    # 2360. 图中的最长环\n",
    "    # !求内向基环树(每个点出度最多为1)的最大环\n",
    "    class Solution:\n",
    "        def longestCycle(self, edges: List[int]) -> int:\n",
    "            \"\"\"\n",
    "            每个节点至多有一条出边\n",
    "            外向基环树最大环\n",
    "            \"\"\"\n",
    "            n = len(edges)\n",
    "            adjList = [[] for _ in range(n)]\n",
    "            deg = [0] * n\n",
    "            for u, v in enumerate(edges):\n",
    "                if v == -1:\n",
    "                    continue\n",
    "                adjList[u].append(v)\n",
    "                deg[v] += 1\n",
    "\n",
    "            cycle, *_ = cyclePartition(n, adjList, isDirected=True)\n",
    "            return max((len(g) for g in cycle), default=-1)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def longestCycle(self, edges: List[int]) -> int:\n",
    "        ans=-1\n",
    "        n=len(edges)\n",
    "        vis=[0 for i in range(n)]\n",
    "        def check(x):\n",
    "            nonlocal ans\n",
    "            tot=1\n",
    "            i=x\n",
    "            while edges[i]!=x:\n",
    "                i=edges[i]\n",
    "                tot+=1\n",
    "            ans=max(ans,tot)\n",
    "        def dfs(x):\n",
    "            if vis[x]==0:\n",
    "                if edges[x]!=-1:\n",
    "                    vis[x]=1\n",
    "                    dfs(edges[x])\n",
    "                    vis[x]=2\n",
    "                else:\n",
    "                    vis[x]=2\n",
    "            elif vis[x]==1:\n",
    "                check(x)\n",
    "                vis[x]=2\n",
    "            else:\n",
    "                vis[x]=2\n",
    "        for i in range(n):\n",
    "            if vis[i]==0:\n",
    "                dfs(i)\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def longestCycle(self, edges: List[int]) -> int:\n",
    "        n = len(edges)\n",
    "        vis = [0] * n\n",
    "        ans = -1\n",
    "\n",
    "        def dfs(x, path):\n",
    "            if vis[x] == 2: return\n",
    "            if vis[x] == 1:\n",
    "                nonlocal ans\n",
    "                idx = path.index(x)\n",
    "                ans = max(ans, len(path) - idx)\n",
    "                return\n",
    "\n",
    "            if edges[x] == -1: return\n",
    "            \n",
    "            vis[x] = 1\n",
    "            path.append(x)\n",
    "            dfs(edges[x], path)\n",
    "            vis[x] = 2\n",
    "        \n",
    "        for i in range(n):\n",
    "            dfs(i, [])\n",
    "        \n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def longestCycle(self, edges: List[int]) -> int:\n",
    "        n = len(edges)\n",
    "        g = [[] for _ in range(n)]\n",
    "        deg = [0] * n\n",
    "        for i, x in enumerate(edges):\n",
    "            if x != -1:\n",
    "                g[i].append(x)\n",
    "                deg[x] += 1\n",
    "        q = deque()\n",
    "        for i, x in enumerate(deg):\n",
    "            if x == 0:\n",
    "                q.append(i)\n",
    "        while q:\n",
    "            e = q.popleft()\n",
    "            for x in g[e]:\n",
    "                deg[x] -= 1\n",
    "                if deg[x] == 0:\n",
    "                    q.append(x)\n",
    "        ans = -1\n",
    "        time = [-1] * n\n",
    "        def dfs(node: int, t: int):\n",
    "            time[node] = t\n",
    "            for ee in g[node]:\n",
    "                if deg[ee] == 0:\n",
    "                    continue\n",
    "                if time[ee] == -1:\n",
    "                    dfs(ee, t + 1)\n",
    "                else:\n",
    "                    nonlocal ans\n",
    "                    ans = max(ans, t - time[ee] + 1)\n",
    "        for i, x in enumerate(deg):\n",
    "            if x != 0 and time[i] == -1:\n",
    "                dfs(i, 0)\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def longestCycle(self, edges: List[int]) -> int:\n",
    "        visited = [False]*len(edges)\n",
    "\n",
    "        def dfs(node):\n",
    "            if visited[node]:\n",
    "                return set([node]),False\n",
    "            else:\n",
    "                visited[node]=True\n",
    "                if edges[node]==-1:\n",
    "                    return set(),False\n",
    "                loop_path,has_loop = dfs(edges[node])\n",
    "                # print(node,loop_path,has_loop)\n",
    "                if has_loop or node in loop_path:\n",
    "                    return loop_path,True\n",
    "                else:\n",
    "                    loop_path.add(node)\n",
    "                    return loop_path,False\n",
    "                \n",
    "        max_loop = -1\n",
    "        for i in range(len(edges)):\n",
    "            if not visited[i]:\n",
    "                loop_path,has_loop = dfs(i)\n",
    "                if has_loop:\n",
    "                    max_loop = max(max_loop,len(loop_path))\n",
    "\n",
    "        return max_loop\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def longestCycle(self, edges: List[int]) -> int:\n",
    "        n = len(edges)\n",
    "        visited = [False] * n\n",
    "        inStack = [False] * n\n",
    "        stack = []\n",
    "        def dfs(node):\n",
    "            if edges[node] == -1: \n",
    "                return -1\n",
    "            if inStack[node]:\n",
    "                for i in reversed(range(len(stack))):\n",
    "                    if stack[i] == node:\n",
    "                        break\n",
    "                return len(stack) - i\n",
    "            if visited[node]:\n",
    "                return -1\n",
    "            \n",
    "            visited[node] = True\n",
    "            inStack[node] = True\n",
    "            stack.append(node)\n",
    "            loopLen = dfs(edges[node])\n",
    "            stack.pop()\n",
    "            inStack[node] = False\n",
    "            return loopLen\n",
    "            \n",
    "        ans = -1\n",
    "        for node in range(n):\n",
    "            if not visited[node]:\n",
    "                ans = max(ans, dfs(node))\n",
    "\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def longestCycle(self, edges: List[int]) -> int:\n",
    "        indegree = defaultdict(int)\n",
    "        relation = defaultdict(list)\n",
    "        node_num = len(edges)\n",
    "        for num, val in enumerate(edges):\n",
    "            if val == -1:\n",
    "                continue\n",
    "            indegree[val] += 1\n",
    "            relation[num].append(val)\n",
    "        # print(relation,indegree)\n",
    "        q = [x for x in range(node_num) if x not in indegree]\n",
    "        # print(q)\n",
    "        visit = set()\n",
    "        while q:\n",
    "            v = q.pop()\n",
    "            node_num -= 1\n",
    "            for i in relation.get(v, []):\n",
    "                indegree[i] -= 1\n",
    "                if indegree[i] == 0:\n",
    "                    q.append(i)\n",
    "        if node_num == 0:\n",
    "            return -1\n",
    "        # print(indegree)\n",
    "\n",
    "        not_zero =  [x for x in indegree if indegree[x] != 0]\n",
    "        ans = 0\n",
    "        for i in not_zero:\n",
    "            if i in visit:\n",
    "                continue\n",
    "            step = 0\n",
    "            def bfs(node):\n",
    "                # print(\"node:\", node)\n",
    "                nonlocal step\n",
    "                if node in visit:\n",
    "                    # print(\"step:\", step)\n",
    "                    return step\n",
    "                visit.add(node)\n",
    "                node = relation[node][0]\n",
    "                # print(\"visit:\", visit)\n",
    "                step += 1\n",
    "                return bfs(node)\n",
    "\n",
    "            ans = max(ans, bfs(i))\n",
    "            step = 0\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def longestCycle(self, edges: List[int]) -> int:\n",
    "        n = len(edges)\n",
    "        dic = defaultdict(int)\n",
    "        visited = [False] * n\n",
    "        ans = -1\n",
    "        def dfs(node: int, level: int):\n",
    "            if node in dic:\n",
    "                nonlocal ans\n",
    "                ans = max(ans, level - dic[node])\n",
    "                return\n",
    "            if visited[node]: return\n",
    "            dic[node] = level\n",
    "            visited[node] = True\n",
    "            if edges[node] != -1:\n",
    "                dfs(edges[node], level + 1)\n",
    "\n",
    "        for i in range(n):\n",
    "            if visited[i]: continue\n",
    "            dic.clear()\n",
    "            dfs(i, 0)\n",
    "        return ans\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def longestCycle(self, edges: List[int]) -> int:\n",
    "        indegree = defaultdict(int)\n",
    "        relation = defaultdict(list)\n",
    "        node_num = len(edges)\n",
    "        for num, val in enumerate(edges):\n",
    "            if val == -1:\n",
    "                continue\n",
    "            indegree[val] += 1\n",
    "            relation[num].append(val)\n",
    "        print(relation,indegree)\n",
    "        q = [x for x in range(node_num) if x not in indegree]\n",
    "        # print(q)\n",
    "        visit = set()\n",
    "        while q:\n",
    "            v = q.pop()\n",
    "            node_num -= 1\n",
    "            for i in relation.get(v, []):\n",
    "                indegree[i] -= 1\n",
    "                if indegree[i] == 0:\n",
    "                    q.append(i)\n",
    "        if node_num == 0:\n",
    "            return -1\n",
    "        # print(indegree)\n",
    "\n",
    "        not_zero =  [x for x in indegree if indegree[x] != 0]\n",
    "        ans = 0\n",
    "        for i in not_zero:\n",
    "            if i in visit:\n",
    "                continue\n",
    "            step = 0\n",
    "            def bfs(node):\n",
    "                # print(\"node:\", node)\n",
    "                nonlocal step\n",
    "                if node in visit:\n",
    "                    print(\"step:\", step)\n",
    "                    return step\n",
    "                visit.add(node)\n",
    "                node = relation[node][0]\n",
    "                # print(\"visit:\", visit)\n",
    "                step += 1\n",
    "                return bfs(node)\n",
    "\n",
    "            ans = max(ans, bfs(i))\n",
    "            step = 0\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def longestCycle(self, edges: List[int]) -> int:\n",
    "        N = len(edges)\n",
    "        visited = [False]*N\n",
    "        res = -1\n",
    "\n",
    "        def dfs(i, seen):\n",
    "            nonlocal res\n",
    "            if visited[i]:\n",
    "                return\n",
    "            \n",
    "            visited[i] = True\n",
    "\n",
    "            nxt = edges[i]\n",
    "            if nxt == -1:\n",
    "                return\n",
    "\n",
    "            if nxt in seen:\n",
    "                res = max(res,seen[i]+1-seen[nxt])\n",
    "            else:\n",
    "                seen[nxt] = seen[i]+1\n",
    "                dfs(nxt, seen)\n",
    "                \n",
    "        for i in range(N):\n",
    "            dfs(i, {i:0})\n",
    "        \n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def longestCycle(self, edges: List[int]) -> int:\n",
    "        def dfs(node, d, dis):\n",
    "            nonlocal ret\n",
    "            dis[node] = d\n",
    "            vst[node] = 1\n",
    "            to = edges[node]\n",
    "            if to != -1:\n",
    "                pre = dis.get(to, 0)\n",
    "                if pre:\n",
    "                    ret = max(ret, d - pre + 1)\n",
    "                else:\n",
    "                    if not vst[to]:\n",
    "                        dfs(to, d + 1, dis)\n",
    "        n = len(edges)\n",
    "        # vst = [0] * n\n",
    "        # dis = [0] * n\n",
    "        ret = -1\n",
    "        deg = [0] * n\n",
    "        for i in range(n):\n",
    "            if edges[i] != -1:\n",
    "                deg[edges[i]] += 1\n",
    "        # print(deg)\n",
    "        q = []\n",
    "        vst = [0] * n\n",
    "        for i in range(n):\n",
    "            if deg[i] == 0:\n",
    "                q.append(i)\n",
    "                vst[i] = 1\n",
    "        while q:\n",
    "            tmp = q\n",
    "            # print(q, '----')\n",
    "            q = []\n",
    "            for x in tmp:\n",
    "                to = edges[x]\n",
    "                if to != -1:\n",
    "                    deg[to] -= 1\n",
    "                    if deg[to] == 0:\n",
    "                        q.append(to)\n",
    "                        vst[to] = 1\n",
    "        # print([i for i in range(n) if not vst[i]])\n",
    "        for i in range(n):\n",
    "            if not vst[i]:\n",
    "                dis = {}\n",
    "                dfs(i, 1, dis)\n",
    "        return ret"
   ]
  }
 ],
 "metadata": {},
 "nbformat": 4,
 "nbformat_minor": 2
}
